Functional hardware verification is often carried out by subjecting the verified design to multiple random test cases, which comply with a given specification. Random test case generation is sometimes formulated as a constraint satisfaction problem (CSP). Generally, when expressing a problem as a CSP, the problem is specified in terms of a set of variables, each of which can assume values in a given domain, and a set of constraints that the variables should simultaneously satisfy. Each constraint may be expressed as a relation, defined over some subset of the variables, denoting valid combinations of their values. A solution to the problem is an assignment of a value to each variable from its domain that satisfies all of the constraints.
An exemplary test generator, which uses CSP solving techniques for generating random test cases is described by Adir et al., in “Genesys-Pro: Innovation in Test Program Generation for Functional Processor Verification,” IEEE Design & Test of Computers, (21:2), March-April, 2004, pages 84-92. CSP-based random test generation methods are also described by Bin et al., in “Using Constraint Satisfaction Formulation and Solution Techniques for Random Test Program Generation,” IBM Systems Journal, (41:3), August, 2002, pages 386-402. The paper shows methods for modeling random test program generation as a CSP, and describes a set of solution techniques that are used in practical test-case generation tools.
Optimization methods are used in a variety of applications for determining the optimal solution of a mathematical problem. Applications of optimization methods include, for example, worker shift planning, flow problems, packaging problems, time-table optimization, resource allocation, financial optimization problems and many others. In a typical optimization task, the problem is expressed using a set of constraints defined over variables, and an objective function defined over at least some of the variables. The optimization process seeks a solution that satisfies the constraints, while maximizing or minimizing the objective function.
Several optimization methods and tools are known in the art. For example, ILOG, Inc. (Mountain View, Calif.), offers an optimization tool called CPLEX, for solving linear, mixed-integer and quadratic programming problems. Details regarding this product are available at www.ilog.com/products/cplex. As another example, Dash Optimization, Inc. (Englewood Cliffs, N.J.), offers a modeling and optimization suite called Xpress-MP. Details regarding this product can be found at www.dashoptimization.com.